package Classic150;

import LinkedList.ListNode;

public class 随机链表的复制 {
    /*
        在每一个节点后添加复制节点，再分阶段进行操作
     */
    public ListNode copyRandomList(ListNode head) {
        if (head == null) return null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = new ListNode(cur.val);
            cur.next.next = next;
            cur = next;
        }
        cur = head;
        while (cur != null) {
            if (cur.random == null) cur.next.random = null;
            else cur.next.random = cur.random.next;
            cur = cur.next.next;
        }
        cur = head;
        ListNode newHead = head.next;
        ListNode cur2 = newHead;
        while (cur != null) {
            cur.next = cur2.next;
            cur = cur.next;
            if (cur != null) {
                cur2.next = cur.next;
                cur2 = cur.next;
            }
        }
        return newHead;
    }
}
